<head>
    <meta charset="UTF-8">
<title>算法提高 金属采集</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <div class="sec_header">
问题描述</div>
<div class="sec_cont">
	<p>人类在火星上发现了一种新的金属！这些金属分布在一些奇怪的地方，不妨叫它节点好了。一些节点之间有道路相连，所有的节点和道路形成了一棵树。一共有 n 个节点，这些节点被编号为 1~n 。人类将 k 个机器人送上了火星，目的是采集这些金属。这些机器人都被送到了一个指定的着落点， S 号节点。每个机器人在着落之后，必须沿着道路行走。当机器人到达一个节点时，它会采集这个节点蕴藏的所有金属矿。当机器人完成自己的任务之后，可以从任意一个节点返回地球。当然，回到地球的机器人就无法再到火星去了。我们已经提前测量出了每条道路的信息，包括它的两个端点 x 和 y，以及通过这条道路需要花费的能量 w 。我们想花费尽量少的能量采集所有节点的金属，这个任务就交给你了。</p>
</div>
<div class="sec_header">
输入格式</div>
<div class="sec_cont">
	<p>第一行包含三个整数 n, S 和 k ，分别代表节点个数、着落点编号，和机器人个数。</p>
	<p>接下来一共 n-1 行，每行描述一条道路。一行含有三个整数 x, y 和 w ，代表在 x 号节点和 y 号节点之间有一条道路，通过需要花费 w 个单位的能量。所有道路都可以双向通行。</p>
</div>
<div class="sec_header">
输出格式</div>
<div class="sec_cont">
	输出一个整数，代表采集所有节点的金属所需要的最少能量。
</div>
<div class="sec_header">
样例输入</div>
<div class="sec_text">
6 1 3<br />
1 2 1<br />
2 3 1<br />
2 4 1000<br />
2 5 1000<br />
1 6 1000
</div>
<div class="sec_header">
样例输出</div>
<div class="sec_text">
3004
	</div>
<div class="sec_header">
样例说明</div>
<div class="sec_cont">
	<p>所有机器人在 1 号节点着陆。</p>
	<p>第一个机器人的行走路径为 1-&gt;6 ，在 6 号节点返回地球，花费能量为1000。</p>
	<p>第二个机器人的行走路径为 1-&gt;2-&gt;3-&gt;2-&gt;4 ，在 4 号节点返回地球，花费能量为1003。</p>
	<p>第一个机器人的行走路径为 1-&gt;2-&gt;5 ，在 5 号节点返回地球，花费能量为1001。</p>
</div>
<div class="sec_header">
数据规模与约定</div>
<div class="sec_cont">
	<p>本题有10个测试点。
	<p>对于测试点 1~2 ， n &lt;= 10 ， k &lt;= 5 。</p>
	<p>对于测试点 3 ， n &lt;= 100000 ， k = 1 。</p>
	<p>对于测试点 4 ， n &lt;= 1000 ， k = 2 。</p>
	<p>对于测试点 5~6 ， n &lt;= 1000 ， k &lt;= 10 。</p>
	<p>对于测试点 7~10 ， n &lt;= 100000 ， k &lt;= 10 。</p>
	<p>道路的能量 w 均为不超过 1000 的正整数。</p>
</div>
